package Leetcode.树;

import javafx.util.Pair;

/**
 * @ClassName 最深叶节点的最近公共祖先
 * @since: 2023/9/6 15:05
 * @auth: kirito
 * @description:
 **/
public class 最深叶节点的最近公共祖先 {
    private TreeNode ans;
    private int maxDepth = -1; // 全局最大深度

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    private int dfs(TreeNode node, int depth) {
        // 维护全局最大深度
        if (node == null) {
            maxDepth = Math.max(depth, maxDepth);
            return depth;
        }
        // 获取左子树最深叶节点的深度
        int leftMax = dfs(node.left, depth + 1);
        // 获取右子树最深叶节点的深度
        int rightMax = dfs(node.right, depth + 1);

        if (leftMax == rightMax && leftMax == maxDepth) {
            ans=node;
        }
        // 当前子树最深叶节点的深度
        return Math.max(leftMax, rightMax);
    }

}
